package com.alex.algorithm.medium;

public class LongestPalindromicString {
    public static void main(String[] args) {
        System.out.println(longestPalindromic("babad"));
        System.out.println(longestPalindromic("cbbd"));
    }

    private static CharSequence longestPalindromic(CharSequence sequence) {
        CharSequence res = sequence.subSequence(0,1);
        boolean[][] dp = new boolean[sequence.length()][];
        for (int i = sequence.length() -1; i >= 0; i--) {
            dp[i] = new boolean[sequence.length()];
            for (int j = i; j < sequence.length(); j++) {
                if (i == j){
                    dp[i][j] = true;
                }else if (j - i == 1 && sequence.charAt(i) == sequence.charAt(j)) {
                    dp[i][j] = true;
                }else if (dp[i+1][j-1] && sequence.charAt(i) == sequence.charAt(j)) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j - i + 1 > res.length()) {
                    res = sequence.subSequence(i,j + 1);
                }
            }
        }
        return res;
    }
}
